package sortingAlgorithms;

import javax.swing.*;
import java.io.*;
public class sorting {

	private static void readfile(String path,String[]r,int linum)throws IOException,FileNotFoundException {
		File f=new File(path);
		FileInputStream fin=new FileInputStream(f);
		InputStreamReader h=new InputStreamReader(fin);
		BufferedReader l=new BufferedReader(h);
		for(int i=0;i<linum;i++){
		r[i]=l.readLine();
		}
		
	}
	private static void srt(int f,int l,double[]A,int []count){
		if (l==f){}//stopping condition
	else{int p=((f+l)/2);
	srt(f,p,A,count);
	srt((p+1),l,A,count);
	mrg(f,p,p+1,l,A,count);
	}
		
		
	}
	private static void mrg(int f1,int l1,int f2,int l2,double[]numbers,int[]count){
		double[]C=new double[numbers.length];
		
		
		int fa=f1;int fb=f2;int i=fa;
		
		while(fb<=l2 && fa<=l1){	
			if(numbers[fa]<numbers[fb]){C[i]=numbers[fa];fa++;i++;}
			else {C[i]=numbers[fb];fb++;i++;}
		count[1]++;	
		}
		count[1]++;
		if(fa>l1&&fb>l2){}
		else if(fb>l2){
			count[1]++;
			for(int j=i;j<=l2;j++){
				C[j]=numbers[fa];
				if(fa<l1)fa++;
				else break;
			}
		}
		else{
			for(int j=i;j<=l2;j++){
				C[j]=numbers[fb];
				if(fb<l2)fb++;
				else break;
			}
		}
		for(int j=f1;j<=l2;j++){
			numbers[j]=C[j];
		}
	
	}
	
	
	
	private static void srt(int lo,int piv,int hi,double[]list){
		
		//Stopping condition:
		if(lo==hi){}
		
		else if(piv==hi){
			
			int pivnow=pivplace(lo,piv-1,list);
			
			srt(lo,pivnow,piv-1,list);
			
			srt(hi,hi,hi,list);
			
		}
		else if(piv==lo){
			
			srt(lo,lo,lo,list);
			
			int pivthen=pivplace(piv+1,hi,list);
			
			srt(piv+1,pivthen,hi,list);
		}
		else{
	
		
		int pivnow=pivplace(lo,piv,list);
		
		srt(lo,pivnow,piv,list);
		
		int pivthen=pivplace(piv+1,hi,list);
		
		srt(piv+1,pivthen,hi,list);
		
		
	}
	}
	
	
	
	
	private static int pivplace(int lo,int hi,double[]list){
		
		if(lo==hi){return lo;}
		else{
		boolean go2=false;int piv=lo;
		do{
			while(!go2)
			{
				if(list[lo]>list[hi]){
					double temp=list[lo];
					list[lo]=list[hi];
					list[hi]=temp;
					go2=true;
					lo++;
					piv=hi;
				}
				else {
					if(hi<=lo)break;
				    hi--;
				}
			}
			go2=false;
			
			while(!go2){
				if(list[hi]<list[lo]){
					double temp=list[lo];
					list[lo]=list[hi];
					list[hi]=temp;
					go2=true;
					hi--;
					piv=lo;
				}
				else {
					if(lo>=hi)break;
				    lo++;
				}
			}
			
		}while(lo<hi);
			
			go2=false;
			
		

	return piv;
		}	
	}	

private static void bin (double[]intnum){
    int itrno=0;int cmprsn=0;
	 for(int j=(intnum.length-2);j>=0;j--){
	 	for(int i=0;i<=j;i++){
	 		itrno++;
	 		if(intnum[i]>intnum[i+1]){
	 		    double temp=intnum[i];
	 		    intnum[i]=intnum[i+1];
	 		    intnum[i+1]=temp;
	 		}
	 		
	 		itrno++;cmprsn++;
	 	}
	 }
	
	 for (int t=0;t<=(intnum.length-1);t++){
		 System.out.println(intnum[t]);
		} 
	 System.out.println("total no. of itrations = "+itrno);
	 System.out.println("no. of comparisons ="+cmprsn);
}

private static void shl (double[]intnum){
    
    int d=((int)(intnum.length/2));int count=0;
    int itrno=0;int cno=0;
while(d>0){ 
 for(int j=0;j<=(intnum.length-(1+d));j++){
   		 if(intnum[j]>intnum[j+d]){
   			 double temp1=intnum[j];
   			 intnum[j]=intnum[j+d];
   			 intnum[j+d]=temp1;
   			 count++;itrno++;cno++;
   		 }
   		 itrno++;
 }
   		
   	if(count==0)d/=2;
   	count=0;itrno++;cno++;
}

    
  //printing the sorted array
    for (int i=0;i<=(intnum.length-1);i++){
		 System.out.println(intnum[i]);
		} 
	
    System.out.println("total no of itrations = "+itrno);
  System.out.println("total no of comparisons = "+cno);
}
	
private static void quick (double[]intnum){
	
	int piv=pivplace(0,intnum.length-1,intnum);
	srt(0,piv,intnum.length-1,intnum);
	
	
	for (int i=0;i<intnum.length;i++){
	System.out.println(intnum[i]);
	}
}
	
private static void msrt (double[]intnum){
    
    int[]count=new int[2];
    
	srt(0,intnum.length-1,intnum,count);
	
	
	for(int i=0;i<intnum.length;i++){
		System.out.println(intnum[i]);
	}
	System.out.println("no. of iterations = "+count);
}

public static void main (String args[])throws IOException,FileNotFoundException{
	String[]num={"","",""};int count=0;
	String ch=JOptionPane.showInputDialog("i wanna to: 1.read elements from a file. "+
			"2.enter data manually.");
	int cho=Integer.parseInt(ch);
	 int cmaordr=-1; String list="";
	 switch(cho){
	 
	 case 1:{
		 String path=JOptionPane.showInputDialog("Enter the file's path (including its name) please");
		 File f=new File(path);
			FileInputStream fin=new FileInputStream(f);
			InputStreamReader h=new InputStreamReader(fin);
			BufferedReader l=new BufferedReader(h);
			String linums=l.readLine();
			int linum=Integer.parseInt(linums);
			num=new String[linum];
		readfile(path,num,linum);
		 break;
	 }
	 case 2:{	
		String input=JOptionPane.showInputDialog("enter a number list separated by commas");
		
		if (input.indexOf(",")==-1)System.out.print(input);
		else{
	    list=input.trim();
	    //removing 1st and last comma(s) (if exist(s)):
	    int a=list.indexOf(",");
	    int b=list.lastIndexOf(",");
	    int c=list.length();
	    if(a==0 && c==(b+1)){
	      list=list.substring(1,b);
		}
	    else if(a==0 && c>(b+1)){
	        list=list.substring(1,c);
		}
	    else if(a>0 && b==(c-1)){
	        list=list.substring(0,b);
	}
	    //detriminig number of commas:
	    
	    int lstcma=list.lastIndexOf(",");
	    do{
	    	cmaordr=list.indexOf(",",cmaordr+1);
	    	count++;
	    }
	    while(cmaordr<lstcma);
	    //charging the items into a string array:
	     num=new String[count+1];cmaordr=-1;
	     for(int i=0;i<(count);i++){
	    	 int temp1=cmaordr+1;
	    	 cmaordr=list.indexOf(",",(cmaordr+1));
	    	 String temp3=list.substring(temp1,(cmaordr));
	    num[i]=temp3;
	    }
	     num[count]=list.substring((cmaordr+1),list.length());
		}
		break;
	 }
	 default :{
		 JOptionPane.showMessageDialog(null,"u didnt chose andy thing");
	 }
	 }
	     //casting the string array to adouble one:

		double[]intnum=new double[num.length];
	     for(int i=0;i<(num.length);i++){
	     intnum[i]=Double.parseDouble(num[i]);
		}
	     
	     //now chosing the sorting technique:
		String chice=JOptionPane.showInputDialog("Which of the following tichniques " +
				"u wich to apply?: 1.binary 2.shell 3.quick 4.merge sort");
		int choice=Integer.parseInt(chice);
		switch(choice){
		case 1:{
			bin(intnum);
			break;
		}
		case 2:{
			shl(intnum);
			break;
		}
		case 3:{
			quick(intnum);
			break;
		}
		case 4:{
			msrt(intnum);
			break;
		}
		default:
			JOptionPane.showMessageDialog(null,"sorry the program will end " +
					"you didn't chose any operation to perform!");
		    break;
		
		}	
	}

}




